package org.example;

import java.util.*;

public class Test7 {
    //leetcode 15 三数之和 https://leetcode.cn/problems/3sum/description/

    /**
     * 这道题目解决问题的关键是去重，将数组进行排序，每次固定一个数字i，当nums[i] == nums[i+1]的时候，跳过本次遍历
     * j和k也是如此，跳过重复值
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n-2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int target = 0 - nums[i];
            int j = i + 1, k = n - 1;
            while (j < k) {
                if (nums[j] + nums[k] < target) j++;
                else if (nums[j] + nums[k] > target) k--;
                else {
                    ret.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    while (j < k - 1 && nums[j] == nums[j + 1]) j++;
                    while (k > j + 1 && nums[k] == nums[k - 1]) k--;
                    j++;
                    k--;
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        Test7 test7 = new Test7();
        int[] arr = {-1,0,1,2,-1,-4};
        test7.threeSum(arr);
        System.out.println(666);
    }
}
